/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //若输入仅有1个或0个结点，直接返回
        if(!head || !(head->next))  return head;
        /*
        直接法：创建数组将链表中的节点信息保存下来，当到达链表尾端时，再进行反转
        时间复杂度O(n + n):需遍历两次链表；空间复杂度O(n)：需要一个数组存储链表信息
        */
        vector<ListNode*> numsOfList;
        ListNode* pHead = head;
        while(pHead->next){
            numsOfList.push_back(pHead);
            pHead = pHead->next;
        }

        //开始反转链表，此时head变成链表头部
        int length = numsOfList.size() - 1;
        pHead->next = numsOfList[length];
        for(int i = length; i > 0; --i){
            numsOfList[i]->next = numsOfList[i - 1];
        }
        numsOfList[0]->next = NULL;

        return pHead;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //若输入仅有1个或0个结点，直接返回
        if(!head || !(head->next))  return head;
        /*
        顺序反转：每个节点的反转需要三个信息（当前节点、前一个节点以及后一个节点）
        时间复杂度O(n):需遍历一次链表；空间复杂度O(1)
        */

        ListNode* pHead = head;  //记录当前要反转的节点，最终指向新链表的表头
        ListNode* pPrior = NULL;  //用于每次反转中暂存当前节点的前一个节点信息
        ListNode* pNext = head->next;  //用于每次反转中暂存当前节点的next

        while(pNext){
            pHead->next = pPrior;  //反转链表
            pPrior = pHead;
            pHead = pNext;
            pNext = pHead->next;
        }

        pHead->next = pPrior;
        return pHead;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //若输入仅有1个或0个结点，直接返回
        if(!head || !(head->next))  return head;
        /*
        递归实现链表反转
        */

        ListNode* pHead = head;
        ListNode* pPrior = NULL;

        return reverseList(pHead, pPrior);
    }

    ListNode* reverseList(ListNode* pHead, ListNode* pPrior){
        //传入当前节点以及前一个节点信息，返回新表头信息
        ListNode* newHead = NULL;
        if(pHead->next){
            newHead = reverseList(pHead->next, pHead);
        }else{
            //新表头
            pHead->next = pPrior;
            return pHead;
        }
        pHead->next = pPrior;
        return newHead;
    }
};